package class02;

import java.util.*;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class DoubleEndsQueueToStackAndQueue {
    public static class Node<T>{
        public T value;
        public Node<T> last;
        public Node<T> next;

        public Node(T data){
            value=data;
        }
    }

    public static class DoubleEndsQueue<T>{
        public Node<T> head;
        public Node<T> tail;

        public void addFromHead(T value){
            Node<T> cur = new Node<>(value);
            if (head==null){
                head=cur;
                tail=cur;
            }else {
                cur.next=head;
                head.last=cur;
                head=cur;
            }
        }

        public void addFromBottom(T value){
            Node<T> cur = new Node<>(value);
            if (head==null){
                head=cur;
                tail=cur;
            }else {
                cur.last=tail;
                tail.next=cur;
                tail=cur;
            }
        }

        public T popFromHead(){
            if (head==null)
                return null;
            Node<T> cur = head;
            if (head==tail){
                head=null;
                tail=null;
            }else {
                head=head.next;
                cur.next=null;
                head.last=null;
            }
            return cur.value;
        }

        public T popFromBottom(){
            if (head==null){
                return null;
            }
            Node<T> cur = tail;
            if (head==tail){
                head=null;
                tail=null;
            }else {
                tail=tail.last;
                tail.next=null;
                cur.last=null;
            }
            return cur.value;
        }

        public boolean isEmpty(){
            return head==null;
        }
    }

    public static class MyStack<T>{
        private DoubleEndsQueue<T> queue;

        public MyStack(){
            queue=new DoubleEndsQueue<>();
        }

        public void push(T value){
            queue.addFromHead(value);
        }

        public T pop(){
            return queue.popFromHead();
        }

        public boolean isEmpty(){
            return queue.isEmpty();
        }
    }

    public static class MyQueue<T>{
        private DoubleEndsQueue<T> queue;

        public MyQueue(){
            queue=new DoubleEndsQueue<>();
        }

        public void push(T value){
            queue.addFromHead(value);
        }

        public T poll(){
            return queue.popFromBottom();
        }

        public boolean isEmpty(){
            return queue.isEmpty();
        }
    }

    public static boolean isEqual(Integer o1,Integer o2){
        if (o1==null&&o2!=null)
            return false;
        if (o1!=null&&o2==null)
            return false;
        if (o1==null&&o2==null)
            return true;
        return o1.equals(o2);
    }

    public static void main(String[] args) {
        int oneTestDataNum=100;
        int value = 10000;
        int testTimes = 100000;
        for (int i=0;i<testTimes;i++){
            MyStack<Integer> myStack = new MyStack<>();
            MyQueue<Integer> myQueue = new MyQueue<>();
            Stack<Integer> stack = new Stack<>();
            Queue<Integer> queue = new LinkedList<>();
            for (int j=0;j<oneTestDataNum;j++){
                int nums = (int)(Math.random()*value);
                if (stack.isEmpty()){
                    myStack.push(nums);
                    stack.push(nums);
                }else {
                    if (Math.random()<0.5){
                        myStack.push(nums);
                        stack.push(nums);
                    }else {
                        if (!isEqual(myStack.pop(),stack.pop()))
                            System.out.println("Oops!");
                    }
                }

                int numq = (int)(Math.random()*value);
                if (queue.isEmpty()){
                    myQueue.push(numq);
                    queue.offer(numq);
                }else {
                    if (Math.random()<0.5){
                        myQueue.push(numq);
                        queue.offer(numq);
                    }else {
                        if (!isEqual(myQueue.poll(),queue.poll()))
                            System.out.println("Oops!");
                    }
                }
            }
        }
        System.out.println("finish!");
    }
}
